package com.zjw.algorithm.ready1;


import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
 * <p>
 * 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
 * <p>
 * 如果以下条件满足，我们称这些塔是 美丽 的：
 * <p>
 * 1 <= heights[i] <= maxHeights[i]
 * heights 是一个 山脉 数组。
 * 如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：
 * <p>
 * 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
 * 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]
 * 请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
 */
public class _美丽塔 {


    public static void main(String[] args) {
        System.out.println(new _美丽塔().maximumSumOfHeights(List.of(1000000000, 1000000000, 1000000000)));
    }

    /**
     * 单调栈解决此问题
     */
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int length = maxHeights.size();

        //以i为左边最高点dp
        long[] leftDp = new long[length];
        //以i为右边最高点dp
        long[] rightDp = new long[length];
        //答案ans = Max(leftDp[i]+rightDp[i]-maxHeight[i])i=0..length-1
        //而如何求出dp呢，采用单调栈，一个单调递增，一个单调递减
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < length; i++) {
            //先维护递增栈
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) > maxHeights.get(i)) {
                stack.pop();
            }

            if (stack.isEmpty()) {
                leftDp[i] = (long) maxHeights.get(i) * (i + 1);
            } else {
                leftDp[i] = leftDp[stack.peek()] + (long) maxHeights.get(i) * (i - stack.peek());
            }

            stack.push(i);
        }


        stack.clear();
        for (int i = length - 1; i >= 0; i--) {
            //先维护递增栈
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) > maxHeights.get(i)) {
                stack.pop();
            }

            if (stack.isEmpty()) {
                rightDp[i] = (long) maxHeights.get(i) * (length - i);
            } else {
                rightDp[i] = rightDp[stack.peek()] + (long) maxHeights.get(i) * (stack.peek() - i);
            }

            stack.push(i);
        }


        long ans = 0;
        for (int i = 0; i < length; i++) {
            ans = Math.max(ans, leftDp[i] + rightDp[i] - maxHeights.get(i));
        }

        return ans;
    }
}
